package com.wyw.leetcode.learning.simple;

import java.util.LinkedList;
import java.util.Stack;

/**
 * leetcode topic 20
 *  有效的括号
 *      给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *      有效字符串需满足：
 *          左括号必须用相同类型的右括号闭合。
 *          左括号必须以正确的顺序闭合。
 *          每个右括号都有一个对应的相同类型的左括号。
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 */
public class Topic020 {

    public static void main(String[] args) {
        System.out.println(isValid("([{}])"));
        System.out.println(isValid("[({})"));
        System.out.println(isValid("({[}])"));
        System.out.println(isValid(""));
        System.out.println(isValid("]"));
    }


    public static boolean isValid0(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(Character c : chars) {
            if(c.equals('(') || c.equals('[') || c.equals('{'))
                stack.push(c);
            else {
                if(stack.isEmpty())
                    return false;
                Character pop = stack.pop();
                if(c.equals(')') && !pop.equals('('))
                    return false;
                if(c.equals(']') && !pop.equals('['))
                    return false;
                if(c.equals('}') && !pop.equals('{'))
                    return false;
            }
        }
        return stack.isEmpty();
    }

    public static boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(Character c : chars) {
            if(c.equals('('))
                stack.push(')');
            else if (c.equals('['))
                stack.push(']');
            else if (c.equals('{'))
                stack.push('}');
            else if(stack.isEmpty() || c!= stack.pop())
                return false;

        }
        return stack.isEmpty();
    }

    public static boolean isValid1(String s) {
        if(s.length()%2 ==1){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }

    public static boolean isValid2(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
}

